% Copyright 2011-2015 David Hadka.  All Rights Reserved.
%
% This file is part of the MOEA Framework User Manual.
%
% Permission is granted to copy, distribute and/or modify this document under
% the terms of the GNU Free Documentation License, Version 1.3 or any later
% version published by the Free Software Foundation; with the Invariant Section
% being the section entitled "Preface", no Front-Cover Texts, and no Back-Cover
% Texts.  A copy of the license is included in the section entitled "GNU Free
% Documentation License".

\chapter{Representing Decision Variables}
\label{chpt:representations}

In \chptref{chpt:problems} we saw various ways to define new problems using real-valued (floating-point) decision variables.  In addition to floating-point values, the MOEA Framework allows problems to be encoded using integers, bit strings, permutations, programs (expression trees), and grammars.  This chapter details the use of each of these decision variables and their supported variation operators.  This chapter also details the use of the \java{EncodingUtils} class, which provides many helper methods for creating, reading and modifying different types of decision variables.

\section{Floating-Point Values}
Floating-point values, also known as real-valued decision variables, provide a natural way to represent numeric values.  Floating-point decision variables are represented using \java{RealVariable} decision variables.  When creating a new real-valued decision variable, one must specify the lower and upper bounds that the value can represent.

To create real-valued decision variables, use the \java{EncodingUtils.newReal(lowerBound, upperBound)} method.  Note how the lower and upper bounds must be defined.  The example code below demonstrates creating a solution with three different real-valued decision variables.
\begin{lstlisting}[language=Java]
public Solution newSolution() {
    Solution solution = new Solution(3, 2);
    solution.setVariable(0, EncodingUtils.newReal(-1.0, 1.0));
    solution.setVariable(1, EncodingUtils.newReal(0, Math.PI));
    solution.setVariable(2, EncodingUtils.newReal(10.0, 100.0));
    return solution;
}
\end{lstlisting}

Inside the \java{evaluate} method, we can extract the decision variable values from the solution using the \java{EncodingUtils.getReal(...)} method.  Continuing the previous code example, we extract the values of the three decision variables below.
\begin{lstlisting}[language=Java]
public void evaluate(Solution solution) {
    double x = EncodingUtils.getReal(solution.getVariable(0));
    double y = EncodingUtils.getReal(solution.getVariable(1));
    double z = EncodingUtils.getReal(solution.getVariable(2));
    
    // TODO: evaluate the solution given the values of x, y,
    // and z
}
\end{lstlisting}

Alternatively, if the solution contains exclusively floating-point values, then we can read out all of the variables into an array using a single call.  Note that we pass the entire solution to the \java{EncodingUtils.getReal(...)} method below.
\begin{lstlisting}[language=Java]
public void evaluate(Solution solution) {
    double[] x = EncodingUtils.getReal(solution);
        
    // TODO: evaluate the solution given the values of x[0],
    // x[1], and x[2]
}
\end{lstlisting}

The \java{EncodingUtils} class handles all the type checking and casting needed to ensure variables are read properly.  Attempting to read or write a decision variable that is not the correct type will result in an \java{IllegalArgumentException}.  If you see this exception, check all your decision variables to ensure they are the types you expect.   

\section{Integers}

Integer-valued decision variables can be constructed in a similar way as floating-point values.  For instance, below we construct the solution using calls to \java{EncodingUtils.newInt(lowerBound, upperBound)}.  As we saw with floating-point values, we must specify the lower and upper bounds of the decision variables.
\begin{lstlisting}[language=Java]
public Solution newSolution() {
    Solution solution = new Solution(3, 2);
    solution.setVariable(0, EncodingUtils.newInt(-1, 1));
    solution.setVariable(1, EncodingUtils.newInt(0, 100));
    solution.setVariable(2, EncodingUtils.newInt(-10, 10));
    return solution;
}
\end{lstlisting}

Similarly, the values stored in the decision variables can be read using the \java{EncodingUtils.getInt(...)} method, as demonstrated below.
\begin{lstlisting}[language=Java]
public void evaluate(Solution solution) {
    int x = EncodingUtils.getInt(solution.getVariable(0));
    int y = EncodingUtils.getInt(solution.getVariable(1));
    int z = EncodingUtils.getInt(solution.getVariable(2));
    
    // TODO: evaluate the solution given the values of x, y,
    // and z
}
\end{lstlisting}

And as we saw with floating-point values, if the solution is exclusively represented by integer-valued decision variables, we can likewise extract all values with a single call to \java{EncodingUtils.getInt(...)}.  Note again that this method is passed the entire solution instead of the individual decision variables as before.
\begin{lstlisting}[language=Java]
public void evaluate(Solution solution) {
    int[] x = EncodingUtils.getInt(solution);
        
    // TODO: evaluate the solution given the values of x[0],
    // x[1], and x[2]
}
\end{lstlisting}

The integer representation can be used to represent any other kind of discrete value.  For example, suppose we wanted to represent all even numbers between $0$ and $100$.  We can accomplish this using \java{EncodingUtils.newInt(0, 50)} and reading the value with \java{2*EncodingUtils.getInt(variable)}.  Integers are also useful for selecting a single item from a group.  In this scenario, the integer-valued decision variable represents the index of the item in an array.

\begin{tip}
Internally, integers are stored as floating-point values.  This allows the same variation operators to be applied to both real-valued and integer-valued decision variables.  When working with integers, always use the \java{EncodingUtils.newInt(...)} and \java{EncodingUtils.getInt(...)} methods.  This will ensure the internal floating-point representation is correctly converted into an integer.
\end{tip}

\section{Boolean Values}
Boolean values represent simple binary choices, such as ``yes / no'' or ``on / off''.  Use the \java{EncodingUtils.newBoolean()} method to create boolean decision variables, as shown below.  Note also how we can combine multiple decision variable types in a single solution.
\begin{lstlisting}[language=Java]
public Solution newSolution() {
    Solution solution = new Solution(2, 2);
    solution.setVariable(0, EncodingUtils.newBoolean());
    solution.setVariable(1, EncodingUtils.newInt(0, 100));
    return solution;
}
\end{lstlisting}

Boolean values can be read using \java{EncodingUtils.getBoolean(...)}, as demonstrated below.
\begin{lstlisting}[language=Java]
public void evaluate(Solution solution) {
    boolean b = EncodingUtils.getBoolean(
        solution.getVariable(0));
    int x = EncodingUtils.getInt(solution.getVariable(1));
    
    // TODO: evaluate the solution given the values of b and x
}
\end{lstlisting}

The boolean decision variable works well when the problem has a single choice.  If the problem involves more than one choice, it is more convenient and efficient to use bit strings (an array of booleans) instead.  Bit strings are introduced in the following section.

\section{Bit Strings}
Many problems involve making choices.  For example, the famous knapsack problem involves choosing which items to place in a knapsack to maximize the value of the items carried without exceeding the weight capacity of the knapsack.  If $N$ items are available, we can represent the decision to include each item using a bit string with $N$ bits.  Each bit in the string corresponds to an item, and is set to \java{1} if the item is included and \java{0} if the item is excluded.  For instance, the bit string \java{00110} would place items 3 and 4 inside the knapsack, excluding the rest.

The MOEA Framework supports fixed-length bit strings.  The example code below produces a solution with a single decision variable representing a bit string with length $100$.  Again, note how the entire bit string is stored within a single decision variable.
\begin{lstlisting}[language=Java]
public Solution newSolution() {
    Solution solution = new Solution(1, 2);
    solution.setVariable(0, EncodingUtils.newBinary(100));
    return solution;
}
\end{lstlisting}

When evaluating the solution, the bit string can be read into an array of \java{boolean} values, as demonstrated below.
\begin{lstlisting}[language=Java]
public void evaluate(Solution solution) {
    boolean[] values = EncodingUtils.getBinary(
        solution.getVariable(0));

    //TODO: evaluate the solution given the boolean values
}
\end{lstlisting}

\section{Permutations}
Permutation decision variables appear in many combinatorial and job scheduling problems.  In the famous traveling salesman problem (TSP), a salesman must travel to every city with the condition that they visit each city exactly once.  The order in which the salesman visits each city is conveniently represented as a permutation.  For example, the permutation \java{0,3,1,2} states that the salesman visits the first city first (0 represents the first city), travels to the fourth city (3), then travels to the second city (1), and finally arrives at the third city (2).

The code example below demonstrates the creation of a permutation of 25 elements.
\begin{lstlisting}[language=Java]
public Solution newSolution() {
    Solution solution = new Solution(1, 2);
    solution.setVariable(0, EncodingUtils.newPermutation(25));
    return solution;
}
\end{lstlisting}

The permutation is read out into an array of \java{int} values.  If the permutation is over $N$ elements, the array length will be $N$ and the values stored will range from $0$ to $N-1$.  Each distinct value will appear only once in the array (by definition of a permutation).
\begin{lstlisting}[language=Java]
public void evaluate(Solution solution) {
    int[] permutation = EncodingUtils.getPermutation(
        solution.getVariable(0));
        
    //TODO: evaluate the solution given the permutation
}
\end{lstlisting}

\section{Programs (Expression Trees)}
The first step towards evolving programs using evolutionary algorithms involves defining the rules for the program (i.e., the syntax and semantics).  The MOEA Framework comes enabled with over $45$ pre-defined program elements for defining constants, variables, arithmetic operators, control structures, functions, etc.  When defining the rules, two important properties should be kept in mind: \emph{closure} and \emph{sufficiency}.

The closure property requires all program element to be able to accept as arguments any value and data type that could possibly be returned by any other function or terminal.  All programs generated or evolved by the MOEA Framework are strongly typed.  No program produced by the MOEA Framework will pass an argument to a function that is an incorrect type.  Furthermore, all functions guard against invalid inputs.  For example, the \java{log} of a negative number is undefined.  Rather then causing an error, the \java{log} method will guard itself and return \java{0.0}.  This allows the rest of the calculation to continue unabated.  With these two behaviors built into the MOEA Framework, the closure property is guaranteed.

The sufficiency property states that the rule set must contain all the necessary functions and terminals necessary to produce a solution to the problem.  Ensuring this property holds is more challenging as it will depend on the problem domain.  For instance, the operators \java{And}, \java{Or} and \java{Not} are sufficient to produce all boolean expressions.  It may not be so obvious in other problem domains which program elements are required to ensure sufficiency.  Additionally, it is often helpful to restrict the rule set to those program elements that are sufficient, thus reducing the search space for the evolutionary algorithm.

Below, we construct a rule set using several arithmetic operators.  One terminal is included, the variable \java{x}.  We will assign this variable later when evaluating the program.  The last setting required is the return type of the program.  In this case, the program will return a number.
\begin{lstlisting}[language=Java]
    //first, establish the rules for the program
		Rules rules = new Rules();
		rules.add(new Add());
		rules.add(new Multiply());
		rules.add(new Subtract());
		rules.add(new Divide());
		rules.add(new Sin());
		rules.add(new Cos());
		rules.add(new Exp());
		rules.add(new Log());
		rules.add(new Get(Number.class, "x"));
		rules.setReturnType(Number.class);
\end{lstlisting}

The second step is constructing the solution used by the evolutionary algorithm.  Here, we define one decision variable that is a program following the rule set we previously defined.
\begin{lstlisting}[language=Java]
public Solution newSolution() {
    Solution solution = new Solution(1, 1);
    solution.setVariable(0, new Program(rules));
    return solution;
}
\end{lstlisting}

Lastly, we evaluate the program.  The program executes inside an environment.  The environment holds all of the variables and other identifiers that the program can access throughout its execution.  Since we previously defined the variable \java{x} (with the \java{Get} node), we want to initialize the value of \java{x} in the environment.  Once the environment is initialized, we evaluate the program.  Since we set the return type to be a number in the rule set, we cast the output from the program's evaluation to a number.
\begin{lstlisting}[language=Java]
public void evaluate(Solution solution) {
    Program program = (Program)solution.getVariable(0);

    // initialize the variables used by the program
    Environment environment = new Environment();
    environment.set("x", 15);
    
    // evaluate the program
    double result = (Number)program.evaluate(
        environment)).doubleValue();
        
    // TODO: use the result to set the objective value
}
\end{lstlisting}

\section{Grammars}
Grammars are very similar to programs, but differ slightly in their definition and how the derived programs are generated.  Whereas the program required us to define a set of program elements (the rules) used for constructing the program, the grammar defines these rules using a context free grammar.  The text below shows an example grammar.  The format of this grammar is Backus-Naur form.
\begin{lstlisting}[language=Plaintext]
<expr> ::= <func> | (<expr> <op> <expr>) | <value>
<func> ::= <func-name> ( <expr> )
<func-name> ::= Math.sin | Math.cos | Math.exp | Math.log
<op> ::= + | * | - | /
<value> ::= x
\end{lstlisting}

You should note that this grammar defines the same functions and terminals as the example in the previous section.  This also demonstrates an important difference between programs and grammars in the MOEA Framework.  The grammar explicitly defines where each problem element can appear.  This is in contrast to programs, whose structure is determined by the type system.  As a result, grammars require more setup time but offer more control over programs.  We will now demonstrate the use of grammars in the MOEA Framework.

First, we must parse the context free grammar.  In the example below, the grammar is read from a file.  It is also possible to pass a string containing the grammar using a \java{StringReader} in place of the \java{FileReader}.
\begin{lstlisting}[language=Java]
    ContextFreeGrammar grammar = Parser.load(
        new FileReader("grammar.bnf"));
\end{lstlisting}

Second, we construct the grammar variable that will be evolved by the evolutionary algorithm.  Note how the \java{Grammar} object is passed an integer.  Grammatical evolution uses a novel representation of the decision variable.  Internally, it uses an integer array called a \emph{codon}.  The codon does not define the program itself, but provides instructions for deriving the program using the grammar.  The integer argument to \java{Grammar} specifies the length of the codon.  We defer a detailed explanation of this derivation to the grammatical evolution literature.
\begin{lstlisting}[language=Java]
public Solution newSolution() {
    Solution solution = new Solution(1, 1);
    solution.setVariable(0, new Grammar(10));
    return solution;
}
\end{lstlisting}

Finally, we can evaluate a solution by first extracting the codon and deriving the program.  Unlike programs that can be evaluated directly, the grammar produces a string (the derivation).  While it is common for grammars to produce program code, this is not a requirement.  This is the second major difference between grammars and programs in the MOEA Framework --- the behavior of programs is defined explicitly, whereas the behavior of grammars depend on how the grammar is interpreted.  In this case, we are producing program code and will need a scripting language to evaluate the program.  Using Java's Scripting API and having defined the grammar so that it produces a valid Groovy program, we can evaluate the derivation using the Groovy scripting language.  In the code below, we instantiate a \java{ScriptEngine} for Groovy, initialize the variable \java{x}, and evaluate the program.
\begin{lstlisting}[language=Java]
public void evaluate(Solution solution) {
    int[] codon = ((Grammar)solution.getVariable(0)).toArray();
    
    // derive the program using the codon
    String program = grammar.build(codon);

    if (program == null) {
        // if null, the codon did not produce a valid grammar
        // TODO: penalize the objective value
    } else {
        ScriptEngineManager sem = new ScriptEngineManager();
        ScriptEngine engine = sem.getEngineByName("groovy");

        // initialize the variables used by the program
        Bindings b = new SimpleBindings();
        b.put("x", 15);

        double result = ((Number)engine.eval(program, b))
            .doubleValue();
            
        // TODO: use the result to set the objective value
    }
}
\end{lstlisting}

In order to compile and run this example, the Groovy scripting language must be installed.  To install Groovy, download the binary release from \webpage{http://groovy.codehaus.org/}, extract the \file{embeddable\\groovy-all-2.0.1.jar} file into the \folder{lib} folder in your MOEA Framework installation, and add this jar file onto the Java classpath when launching this example.

\section{Variation Operators}
The MOEA Framework contains a number of variation operators (initialization, mutation, crossover, etc.) tailored for each representation type.  This section provides a brief overview of the available operators and details their use.

\subsection{Initialization}
The start of all evolutionary algorithms is the construction of an initial population.  This population is important since, in general, all future solutions are derived from members of this initial population.  Ensuring this initial population provides a diverse and representative set of individuals is paramount.

The floating-point, integer, binary, permutation and grammar variables are all initialized uniformly at random.  This ensures the values, bit strings, etc. are distributed uniformly throughout the search space.

Programs require a slightly more complicated initialization to ensure the initial population contains a diverse sampling of potential programs.  The MOEA Framework provides the ramped half-and-half initialization method, which is one of the most popular initialization techniques for programs.  We refer readers to the genetic programming literature for a detailed description of ramped half-and-half initialization.

\subsection{Variation (Mutation \& Crossover)}
After the initial population is generated, an evolutionary algorithm evolves the population using individual or combinations of variation operators.  Variation operators are classified into two forms: crossover and mutation.  Crossover involves combining two or more parents to create an offspring.  Mutation involves a single parent.  Mutations generally produce only small changes, but this is not mandatory.

\tblref{tbl:operators} lists the supported variation operators in the MOEA Framework.  The table highlights the decision variable representation and type of each variation operator.

\begin{table}
  \centering
  \caption{List of Supported Variation Operators}
  \label{tbl:operators}
  \begin{tabular}{llll}
    \hline
    Representation & Type & Abbr. \\
    \hline
    Real / Integer & Simulated Binary Crossover & SBX \\
    Real / Integer & Polynomial Mutation & PM \\
    Real / Integer & Differential Evolution & DE \\
    Real / Integer & Parent-Centric Crossover & PCX \\
    Real / Integer & Simplex Crossover & SPX \\
    Real / Integer & Unimodal Normal Distribution Crossover & UNDX \\
    Real / Integer & Uniform Mutation & UM \\
    Real / Integer & Adaptive Metropolis & AM \\
    Binary & Half-Uniform Crossover & HUX \\
    Binary & Bit Flip Mutation & BF \\
    Permutation & Partially-Mapped Crossover & PMX \\
    Permutation & Element Insertion & Insertion \\
    Permutation & Element Swap & Swap \\
    Grammar & Single-Point Crossover for Grammars & GX \\
    Grammar & Uniform Mutation for Grammars & GM \\
    Program & Branch (Subtree) Crossover & BX \\
    Program & Point Mutation & PTM \\
    Any & Single-Point Crossover & 1X \\
    Any & Two-Point Crossover & 2X \\
    Any & Uniform Crossover & UX \\
    \hline
  \end{tabular}
\end{table}

The abbreviation column lists the keyword used in the MOEA Framework for referencing each operator.  The example code below shows how we can specify the operator used by an algorithm and also any parameters for the operator.  In this example, we are using parent-centric crossover (PCX) and setting two of its parameters, \java{pcx.eta} and \java{pcx.zeta}.  Refer to the \java{OperatorFactory} class documentation for a complete list of the operators and their parameters.
\begin{lstlisting}[language=Java]
NondominatedPopulation result = new Executor()
    .withProblem("UF1")
    .withAlgorithm("NSGAII")
    .withProperty("operator", "pcx")
    .withProperty("pcx.eta", 0.1)
    .withProperty("pcx.zeta", 0.1)
    .withMaxEvaluations(10000)
    .run();
\end{lstlisting}

It is also possible to combine certain variation operators using the \java{+} symbol.  In the example below, we combine differential evolution with polynomial mutation (\java{de+pm}), and we can set the parameters for both of these operators as shown.
\begin{lstlisting}[language=Java]
NondominatedPopulation result = new Executor()
    .withProblem("UF1")
    .withAlgorithm("NSGAII")
    .withProperty("operator", "de+pm")
    .withProperty("de.rate", 0.5)
    .withProperty("pm.rate", 0.1)
    .withMaxEvaluations(10000)
    .run();
\end{lstlisting}

\begin{important}
Not all combinations of operators are supported.  In general, combining a crossover operator with a mutation operator is ok.  If you request an invalid operator combination, you will see an exception with the message \emph{invalid number of parents}.  See the \java{CompoundVariation} class documentation for more details on what operators can be combined.
\end{important}

\section{Conclusion}
This chapter introduced the various decision variable representations supported by the MOEA Framework.  Look at these different representations as the building blocks for your problem.  If you can construct your problem using these building blocks, the problem will seamlessly integrate with the MOEA Framework.

We close this chapter by commenting that the MOEA Framework is not limited to these representations.  New representations are periodically introduced in the literature.  This fact influenced the design of the MOEA Framework to allow new representations and variation operators.  Interested readers should stay turned for future updates to this user manual that will discuss such extensions in detail.